Breadth-First Search

Computer Science

Breadth-First Search (BFS)

Traverse all nodes at one level before progressing to the next level. The code uses queues, really.

LevelTraversal([tree](/view/Tree))
     if [tree](/view/Tree) = nil: return
     Queue q
     q.[E](/view/E)nqueue([tree](/view/Tree))
     while not q.[E](/view/E)mpty():
          [nod](/view/Nod)[e](/view/E) <-- q.Dequeue()
          Print([nod](/view/Nod)[e](/view/E))
          if [nod](/view/Nod)[e](/view/E).left =/= nil:
               q.[E](/view/E)nqueue([nod](/view/Nod)[e](/view/E).left)
          if [nod](/view/Nod)[e](/view/E).right =/= nil:
               q.[E](/view/E)nqueue([nod](/view/Nod)[e](/view/E).right)

where [E](/view/E)nqueue is Enqueue

(ALGS201x)